package LeetCode;

import java.util.LinkedList;
import java.util.Queue;

public class LC_662_MaximumWidthofBinaryTree {

    public static void main(String[] args) {

    }

    class Solution {
        public int widthOfBinaryTree(TreeNode root) {
            if (root == null) return 0;
            int re = 1;
            Queue<TreeNode> data = new LinkedList<>();
            data.add(root);
            while (!data.isEmpty()) {
                int n = data.size();
                int cur = 0;
                int count = 0;
                while (n-- > 0) {
                    TreeNode tn = data.poll();
                    if (tn.left != null) {
                        if (count != 0) {
                            count = count + cur + 1;
                            while (cur-- > 0)
                                data.add(new TreeNode(-1));
                        } else
                            count += 1;
                        cur = 0;
                        data.add(tn.left);
                    } else {
                        cur++;
                    }

                    if (tn.right != null) {
                        if (count != 0) {
                            count = count + cur + 1;
                            while (cur-- > 0)
                                data.add(new TreeNode(-1));
                        } else
                            count += 1;
                        cur = 0;
                        data.add(tn.right);
                    } else {
                        cur++;
                    }
                }
                re = re >= count ? re : count;
            }
            return re;
        }
    }

}